import java.util.ArrayList;
import java.util.List;

//https://leetcode.cn/problems/generate-parentheses/
class Solution {
    List<String> ret;
    StringBuffer path;
    int left, right;
    public List<String> generateParenthesis(int n) {
        ret = new ArrayList<>();
        path = new StringBuffer();
        dfs(n);
        return ret;
    }
    public void dfs(int n) {
        if ((left + right) == (2 * n)) {
            ret.add(path.toString());
            return;
        }
        //剪枝
        if (left < n) {
            path.append("(");
            left++;
            dfs(n);
            //回溯 -> 恢复现场
            path.deleteCharAt(path.length() - 1);
            left--;
        }
        //剪枝
        if(right < left) {
            path.append(")");
            right++;
            dfs(n);
            //回溯 -> 恢复现场
            path.deleteCharAt(path.length() - 1);
            right--;
            }    
    }
}